//题目:
// 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
// '.' 匹配任意单个字符
// '*' 匹配零个或多个前面的那一个元素
// 所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

// 示例 1：
// 输入：s = "aa", p = "a"
// 输出：false
// 解释："a" 无法匹配 "aa" 整个字符串。

// 示例 2:
// 输入：s = "aa", p = "a*"
// 输出：true
// 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

// 示例 3：
// 输入：s = "ab", p = ".*"
// 输出：true
// 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    bool isMatch(string s, string p) 
    {
        s=" "+s,p=" "+p;
        int n1=p.size(),n2=s.size();
        //1.创建dp表————dp[i][j]表示：p中[0,i]子串是否覆盖s中[0,j]子串
        vector<vector<bool>> dp(n1,vector<bool>(n2));
        //2.初始化
        dp[0][0]=true;
        for(int i=2;i<n1;i+=2)
        {
            if(p[i]=='*') dp[i][0]=true;
            else break;
        }
        //3.填表
        for(int i=1;i<n1;i++)
        {
            for(int j=1;j<n2;j++)
            {
                // if(p[i]=='*')
                //     dp[i][j]= dp[i-2][j] || (p[i-1]=='.' || p[i-1]==s[j]) && dp[i][j-1];
                // else
                //     dp[i][j]= (p[i]==s[j] || p[i]=='.') && dp[i-1][j-1];

                if((p[i]>='a' && p[i]<='z' && p[i]==s[j]) || p[i]=='.')
                    dp[i][j]=dp[i-1][j-1];
                else if(p[i]=='*' && p[i-1]=='.')
                    dp[i][j]=dp[i-2][j] || dp[i][j-1];
                else if(p[i]=='*')
                    dp[i][j]=dp[i-2][j] || (dp[i][j-1] && p[i-1]==s[j]);
            }
        }
        //4.确定返回值
        return dp[n1-1][n2-1];
    }
};